home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 1870 < prev    next >
Encoding:
Internet Message Format  |  1996-08-06  |  1.3 KB
  1. Path: newsfeed.internetmci.com!xmission!news
  2. From: tknarr@xmission.com  ( Todd Knarr )
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: deque container - how to implement?
  5. Date: 13 Jan 1996 17:05:51 GMT
  6. Organization: Chaos Central
  7. Message-ID: <4d8opf$8hg@news.xmission.com>
  8. References: <4d4c73$qmr@news.xmission.com> <4d71oi$gig@rap.SanDiegoCA.ATTGIS.COM>
  9. Reply-To: tknarr@xmission.com ( Todd Knarr )
  10. NNTP-Posting-Host: slc61.xmission.com
  11. X-Newsreader: IBM NewsReader/2 v1.2
  12.  
  13. >The implementation of a deque uses arrays to provide constant-time
  14. >access, but adds one level of indirection to gain the storage flexibility
  15. >that allows inserts at either end (but not in the middle) to execute
  16. >in constant time.
  17.  
  18. I'll have to pull out the STL source and look at it again, but I thought
  19. the first time I looked at it that you could still invoke an array copy
  20. during an at-end insert when there was no more room in the pointer array.
  21. I can't see any way of avoiding that without going to some sort of a linked
  22. representation, which loses constant-time access.
  23.  
  24. --
  25. Todd Knarr : tknarr@xmission.com      |  finger for PGP public key
  26.                                       |  Member, USENET Cabal
  27.  
  28. Seriously, I don't want to die just yet.  I don't care how
  29. good-looking they are, I! don't! want! to! die!"
  30.                                         -- Megazone ( UF1 )
  31.  
  32.